#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
using namespace std;

/****
 * 1. 写出线性表的结构体 及 线性表快速排序的第一趟排序
 * 2. 写出二叉树的结构体 及 查找二叉树某一指定节点的所有祖先节点
 * */

// 静态顺序表
typedef struct
{
    int *data;
    int MaxSize;
    int length;
} SeqList;

// 第一题: 快速排序第一趟
void QuickSort(SeqList &L)
{

    int i = 0, j = L.length - 1;
    int x = L.data[i];
    while (i < j)
    {
        while (i < j && L.data[j] >= x) // 此两处条件一定要加 '=' 否则若数组中有相同的元素会导致死循环
            j--;
        L.data[i] = L.data[j];
        while (i < j && L.data[i] <= x)
            i++;
        L.data[j] = L.data[i];
    }
    L.data[i] = x;
    // 一趟排序结束 若需要对剩余的排序 递归调用即可
}

// 二叉树
typedef struct TNode
{
    int data;
    TNode *left, *right;
} * Tree, TNode;

// 第二题: 查找祖先结点
bool GetAncestors(Tree &T, int e, vector<TNode> &nodes)
{
    if (T == NULL)
        return false;  // 未找到 回溯

    if (T->data == e)
        return true;   // 找到 回溯

    if (GetAncestors(T->left, e, nodes) || GetAncestors(T->right, e, nodes))
    {
        nodes.push_back(*T); // 子孙结点含有目标节点 入结果集
        return true;
    }

    return false;
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

// 层序遍历
void PrintTree(Tree T)
{
    queue<TNode *> q;
    if (T != NULL)
    {
        q.push(T);
    }
    while (!q.empty())
    {
        printf("%d ", q.front()->data);
        if (q.front()->left != NULL)
            q.push(q.front()->left);

        if (q.front()->right != NULL)
            q.push(q.front()->right);
        q.pop();
    }
}

// 先序遍历
void PrintTree2(Tree T)
{
    if (T == NULL)
        return;
    printf("%d ", T->data);
    PrintTree2(T->left);
    PrintTree2(T->right);
}

int main()
{
    // 第一题
    SeqList L;
    int data[5] = {5,7,3,8,1};
    L.data = data;
    L.length = 5;

    printf("排序前:\n");
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");

    QuickSort(L);

    printf("第一趟排序后:\n");
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");

    printf("\n===================\n");

    Tree T;
    T = NewNode(0);
    T->left = NewNode(1);
    T->right = NewNode(2);
    T->left->left = NewNode(3);
    T->left->right = NewNode(4);
    T->right->left = NewNode(5);

    PrintTree(T);
    printf("\n");

    vector<TNode> v;
    bool res = GetAncestors(T, 4, v);
    if (res) {
        for (int i = 0; i < v.size(); i++) {
            printf("%d ", v[i].data);
        }
    }
    return 0;
}